
# coins = [1, 2, 5]
# 这三枚硬币任意组合找不出来零钱的最小值

# currentChange: 当前能够找出来的零钱的最大值

# currentChange = 0

# 1 currentChange = 1 min: currentChange + 1
# 2 currentChange = 3 min: (currentChange + 1) = 4

# 如果下一枚硬币的面额是 4；
# 如果下一枚硬币的面额 大于 currentChanage + 1；

def non_constructible_change(coins):
  coins.sort()

  current_change = 0

  for coin in coins:
    if coin > current_change + 1:
      return current_change + 1
    
    current_change += coin
  
  return current_change + 1

print(non_constructible_change([1, 2, 5]))